package algorithm.sort;

import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;

public class QuickSort {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(Arrays.toString(solution.sortArray(new int[]{1,2,6,4,5,5,5,8,9})));
    }
    static class Solution {
        public int[] sortArray(int[] nums) {
            quickSort(nums,0,nums.length-1);
            return nums;
        }

        private void quickSort(int[] nums,int l,int r) {
            if (l >= r) return;
            int i = l,j = r;
            ThreadLocalRandom random = ThreadLocalRandom.current();

            int pivot = nums[(l+r)/2];
            while(i<j) {
                while(nums[i] < pivot) {i++;}
                while(nums[j] > pivot) {j--;}
                if(i < j) {
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                    i++;
                    j--;
                }
            }
            quickSort(nums, l, j);
            quickSort(nums, j+1, r);
        }

    }
}
/**
 *
 * 双指针移动:
 *
 * i从左向右移动，寻找第一个大于等于pivot的元素
 * j从右向左移动，寻找第一个小于等于pivot的元素
 * 交换操作:
 *
 * 当找到一对"不合适位置"的元素时(左边有大于pivot的，右边有小于pivot的)
 * 交换这两个元素，使它们回到"正确"的一侧
 * 然后继续推进指针(i++, j--)
 * 终止条件:
 *
 * 当i > j时，分区过程结束
 * 此时，索引j左侧的元素都小于等于pivot
 * 索引i右侧的元素都大于等于pivot
 */
